class Solution {
    public long[] countKConstraintSubstrings(String s, int k, int[][] queries) {
        int n=s.length();
        int left=0;
        int right=0;
        int[] arr=new int[2];
        int[] pLeft=new int[n];
        long[] sum=new long[n+1];
        //预处理出前缀和 和 i位置对应的左下标
        while(right<n){
            int t=s.charAt(right)-'0';
            arr[t]++;
            if(left<right && (arr[0]>k || arr[1]>k)){
                int tt=s.charAt(left)-'0';
                arr[tt]--;
                left++;
            }
            pLeft[right]=left;
            sum[right+1]=sum[right]+right-left+1;
            right++;
        }

        long[] ans=new long[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l=queries[i][0];
            int r=queries[i][1];
            int j=binarySearch(l,r,pLeft);
            ans[i]=sum[r+1]-sum[j]+(long)(j-l+1)*(j-l)/2;
        }
        return ans;
    }
    public int binarySearch(int l,int r,int[] pLeft){
        int mid=0;
        while(l<r){
            mid=l+(r-l)/2;
            if(pLeft[mid]>=r){
                r=mid;
            }else{
                l=mid+1;
            }
        }
        return mid;
    }
}